// https://www.lintcode.com/problem/first-bad-version/my-submissions

/**
 * class SVNRepo {
 *     public:
 *     static bool isBadVersion(int k);
 * }
 * you can use SVNRepo::isBadVersion(k) to judge whether 
 * the kth code version is bad or not.
*/
class Solution {
public:
    /**
     * @param n: An integer
     * @return: An integer which is the first bad version.
     */
    int findFirstBadVersion(int n) {
        int start = 1;
        int end = n;
        while (start + 1 < end)
        {
            int mid = (end - start) / 2 + start;
            if (SVNRepo::isBadVersion(mid)) end = mid;
            else start = mid;
        }
        // if (!SVNRepo::isBadVersion(start) && SVNRepo::isBadVersion(end)) return end;
        // else return start; 
        // 直接这样判断就可以了
        if (SVNRepo::isBadVersion(start)) return start;
        else return end;
    }
};